package ga_yad2;

import genetic_algorithm.Chromosome;
import genetic_algorithm.Crossover;
import genetic_algorithm.Mutation;

import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Map.Entry;

import utils.RandomGenerator;

/**
 * Implements crossover phase of the genetic algorithm
 */
public class Yad2Crossover implements Crossover {

	public static final int SMART = 1;
	public static final int PERMUTATION = 0;

	private int mode; // crossover mode
	
	/**
	 * Constructor- creates a new object implementing crossover phase. 
	 * Crossover is performed according to given crossover mode 
	 * @param mode mode for the crossover
	 */
	public Yad2Crossover(int mode) {
		// set crossover mode
		this.mode = mode;
	}
	
	/**
	 * Gets a pair of parent chromosomes. In chance of crossover-rate, mates
	 * parents (according to the mode which was specified during the
	 * initialization) and mutates them in chance of mutation-rate. If crossover
	 * is not performed, parents are not changed and returned as they are
	 */
	@Override
	public Entry<Chromosome, Chromosome> mate(
			Entry<Chromosome, Chromosome> parents, double crossoverRate,
			Mutation mutator, double mutationRate) {

		// skip crossover in chance of crossover-rate
		if ((RandomGenerator.nextInt(1000) / 1000.0) > crossoverRate) {
			return parents;
		}
		
		// perform crossover according to selected mode
		List<Chromosome> offsprings = null;
		switch (mode) {
		case SMART: {
			offsprings = smartMate(parents.getKey(), parents.getValue());
			break;
		}
		case PERMUTATION: {
			offsprings = permuteCrossover(parents.getKey(), parents.getValue());
			break;
		}
		
		default:
			break;
		}
		
		// mutate the offsprings
		mutator.mutate(offsprings, mutationRate);

		// return resulting offsprings
		return new AbstractMap.SimpleEntry<Chromosome, Chromosome>(
				offsprings.get(0), offsprings.get(1));
	}

	/** TODO
	 * Performs crossover on given parent chromosomes in a single-point manner:
	 * randomly picks an index in the parents' list values; generates first
	 * offspring by concatenating father's prefix with mother's postfix;
	 * generates second offspring by concatenating mother's prefix with father's
	 * postfix
	 * @param father first parent chromosome
	 * @param mother second parent chromosome
	 * @return list containing offsprings chromosmes
	 */	
	private List<Chromosome> permuteCrossover(Chromosome father, Chromosome mother) {
		
		// randomly choose split index
		int numValues = father.getAllValues().size();
		int splitIndex = RandomGenerator.nextInt(numValues);

		// generate values for first offspring
		List<Object> firstOffspringVals = createOffspring(splitIndex, father, mother);
		
		// generate values for second offspring
		List<Object> secondOffspringVals = createOffspring(splitIndex, mother, father);
		
		// generate chromosomes out of offsprings values
		Yad2Chromosome firstOffspring = new Yad2Chromosome(firstOffspringVals);
		Yad2Chromosome secondOffspring = new Yad2Chromosome(secondOffspringVals);
		
		// return resulting chromosomes
		List<Chromosome> offsprings = new ArrayList<Chromosome>();
		offsprings.add(firstOffspring);
		offsprings.add(secondOffspring);
		return offsprings;
	}
	
	private List<Object> createOffspring(int splitIndex, Chromosome source, Chromosome completions) {
		
		// extract prefix from source chromosome
		List<Object> offspringVals = new ArrayList<Object>(source
				.getAllValues().subList(0, splitIndex));
		
		// extract remaining products
		List<Object> remainingProds = new LinkedList<Object>(source
				.getAllValues().subList(splitIndex,
						source.getAllValues().size()));
	
		/* 
		 * complete with non-conflicting values of the other chromosome, 
		 * starting from split position
		 */
		addNonConflicts(splitIndex, completions, remainingProds, offspringVals);
 
		/* 
		 * if there are any remaining products to allocate,
		 * complete with non-conflicting values of the other chromosome, 
		 * starting from chromosome's start
		 */
		if (!remainingProds.isEmpty()) {
			addNonConflicts(0, completions, remainingProds, offspringVals);
		}
		
		return offspringVals;
		
		/*
		 * 1. create a multiset holding all of offspring's missing products
		 * 2. scan each person's product in completions chromosome:
		 * 	a. if product is not in multiset, continue
		 * 	b. if offspring allocates as many products as current person needs, continue
		 * 	c. allocate product to current person
		 * 3. if multiset is not empty:
		 * 	a. scan all products in completions chromosome:
		 * 		i. if product is in multiset, add it to first available person
		 */
	}
	
	private void addNonConflicts(int startIndex, Chromosome completions,
			List<Object> remainingProds, List<Object> offspringVals) {

		int numValues = completions.getAllValues().size();
		for (int i = startIndex ; i < numValues ; ++i) {
			
			// get current product
			Character product = (Character) completions.getValue(i);
			
			// check if can allocate such product
			if (!remainingProds.contains(product)) {
				continue;
			}
			
			// allocate current product to offspring
			offspringVals.add(new Character(product));
			remainingProds.remove(product);
		}
	}
	
	private List<Chromosome> smartMate(Chromosome father, Chromosome mother)
	{
		
		// initialize list to hold each chromosome's genes
		ArrayList<ProductPersonFitness> valueList = new ArrayList<Yad2Crossover.ProductPersonFitness>();
		int numPersons = Yad2Chromosome.productsSplit.size();

		int offset = 0; // current person's offset within product allocation
		int numProducts = 0; // number of products owned by current person

		for (int currPerson = 0 ; currPerson < numPersons ; ++currPerson) // for each person
		{
			offset = Yad2Chromosome.productsSplit.get(currPerson)[Yad2Chromosome.START];
			numProducts = offset + Yad2Chromosome.productsSplit.get(currPerson)[Yad2Chromosome.AMOUNT];
			for (int currProduct = offset; currProduct < numProducts; ++currProduct) // for each product
			{
				// from each chromosome, extract who owns current product and what is its preference
				valueList.add(new ProductPersonFitness((Character)father.getValue(currProduct), currPerson,
						Yad2Fitness.getFitnessOfOneProduct(currPerson, (Character)father.getValue(currProduct))));
				valueList.add(new ProductPersonFitness((Character)mother.getValue(currProduct), currPerson,
						Yad2Fitness.getFitnessOfOneProduct(currPerson, (Character)mother.getValue(currProduct))));
			}
		}
		
		// sort in decreasing order of preference
		Collections.sort(valueList);
		
		// initialize values list for offspring chromosomes
		ArrayList<Object> firstOffspringVals = new ArrayList<Object>();
		ArrayList<Object> secondOffspringVals = new ArrayList<Object>();
		for(int i = 0 ; i < Yad2Chromosome.allProducts.size() ; ++i)
		{
			firstOffspringVals.add(null);
			secondOffspringVals.add(null);
		}
		
		// keep track of product that were not allocated yet
		ArrayList<Character> firstMultiSet = new ArrayList<Character>(Yad2Chromosome.allProducts);
		ArrayList<Character> secondMultiSet = new ArrayList<Character>(Yad2Chromosome.allProducts);
		
		boolean isFirstTurn = true; // indicates if now allocates product to first offspring

		// allocate all parent's products
		for(ProductPersonFitness val : valueList)
		{
			offset = Yad2Chromosome.productsSplit.get(val.person)[Yad2Chromosome.START];
			numProducts = offset + Yad2Chromosome.productsSplit.get(val.person)[Yad2Chromosome.AMOUNT];
			boolean success = false; // indicates if could allocate current product to an offspring
			
			// if now is first offspring's turn, start with the first
			if(isFirstTurn)
			{
				// try allocating current product to first offspring
				success = insertProductsHlper(offset, numProducts,
						firstOffspringVals, firstMultiSet, val);
				
				// if could not, try allocating to second offspring
				if(!success)
				{
					insertProductsHlper(offset, numProducts,
							secondOffspringVals, secondMultiSet, val);
				}
			}
			
			// start with the second offspring
			else if (!isFirstTurn)
			{
				// try allocating current product to second offspring
				success = insertProductsHlper(offset, numProducts,
						secondOffspringVals, secondMultiSet, val);

				// if could not, try allocating to first offspring
				if(!success)
				{
					insertProductsHlper(offset, numProducts,
							firstOffspringVals, firstMultiSet, val);
				}
			}
			
			// switch turns
			isFirstTurn = !isFirstTurn;
		}
		
		// allocate remaining products
		completeFillProductsHelper(firstOffspringVals, firstMultiSet);
		completeFillProductsHelper(secondOffspringVals, secondMultiSet);
		
		
		// generate chromosomes out of offsprings values
		Yad2Chromosome firstOffspring = new Yad2Chromosome(firstOffspringVals);
		Yad2Chromosome secondOffspring = new Yad2Chromosome(secondOffspringVals);

		// return resulting chromosomes
		List<Chromosome> offsprings = new ArrayList<Chromosome>();
		offsprings.add(firstOffspring);
		offsprings.add(secondOffspring);
		return offsprings;
	}

	private void completeFillProductsHelper(
			ArrayList<Object> offspringVals,
			ArrayList<Character> multiSet) {

		// for each remaining product
		for(Character product : multiSet)
		{
			// add product to first empty position
			for(int i = 0 ; i < offspringVals.size() ; ++i)
			{
				if(offspringVals.get(i) == null)
				{
					offspringVals.set(i, product);
					break;
				}
			}
		}
	}

	private boolean insertProductsHlper(int offset, int numProducts,
			ArrayList<Object> offspringVals, ArrayList<Character> multiSet,
			ProductPersonFitness val) {
		boolean success = false;
		
		// for each of given person's products
		for (int currProduct = offset; currProduct < numProducts; ++currProduct) 
		{
			// if current person needs more products and current product has not yet been allocated
			if(offspringVals.get(currProduct) == null && multiSet.contains(val.product))
			{
				// add product at current position
				offspringVals.set(currProduct, val.product);
				multiSet.remove(val.product);
				success = true;
				break;
			}
		}
		
		// return if could add given product
		return success;
	}
	
	private class ProductPersonFitness implements Comparable<ProductPersonFitness>
	{
		public Character product;
		public int	person;
		public Integer fitness;
		
		
		
		public ProductPersonFitness(Character product, int person, int fitness) {
			this.product = product;
			this.person = person;
			this.fitness = fitness;
		}

		@Override
		public int compareTo(ProductPersonFitness o) {
			return fitness.compareTo(o.fitness)*(-1);
		}

		@Override
		public String toString() {
			return "["+ product + ", "
					+ person + ", " + fitness + "]";
		}
		
		
		
	}
}
